#include "ContextFreeGrammar_LR1.h"
#include "FirstFollowGenerator.h"

#include <cassert>
using std::cerr;
using std::endl;

ContextFreeGrammar_LR1::ContextFreeGrammar_LR1(std::istream & in) :
    ContextFreeGrammar(in)
{
    //ctor
    ffg = nullptr;
}

ContextFreeGrammar_LR1::~ContextFreeGrammar_LR1()
{
    //dtor
}

bool ContextFreeGrammar_LR1::MergeListKeepUnique(ClosureList& to, const ClosureList& from)
{
    bool hasChanged = false;
    for(auto itr = from.begin(); itr != from.end(); ++itr)
    {
        bool found = false;

        for(auto jtr = to.begin(); jtr != to.end(); ++jtr)
            if(*jtr == *itr)
            {
                found = true;
                break;
            }

        if(!found)
            to.push_back(*itr), hasChanged = true;
    }
    return hasChanged;
}

void ContextFreeGrammar_LR1::Augment()
{
    std::string nssymbol = GenerateUniqueName(*startSymbol + "_ss");
    auto nssitr = nonterminal.insert(nssymbol).first;

    ProductionList pl = {startSymbol};
    production.insert(std::make_pair(nssymbol, pl));
    startSymbol = nssitr;
}

void ContextFreeGrammar_LR1::AssignFirstFollow(const FirstFollowGenerator * _ffg)
{
    ffg = _ffg;
}

ClosureList ContextFreeGrammar_LR1::GenerateClosure(const ClosureList& closurelist)
{
    cerr << "Generating Closure" << endl ;
    ClosureList newClist = closurelist;
    bool hasChanged = false;
    do
    {
        cerr << "-Iterating" << endl ;
        hasChanged = false;

        for(auto citr = newClist.begin(); citr != newClist.end(); ++citr)
        {
            PrintClosure(*citr, cerr);
            cerr << endl ;

            if(citr->item.dot == citr->item.prod->second.end())
                continue;

            if(!this->isNonterminal(**citr->item.dot))
                continue;

            // Collect FIRST(beta+a)
            bool allEpsilon = true;
            FirstFollowSet beta_a_first;
            for(auto betaitr = std::next(citr->item.dot); betaitr != citr->item.prod->second.end() && allEpsilon; ++betaitr)
            {
                assert(*betaitr != GetEndOfFile() && *betaitr != GetEpsilon());
                ffg->CollectFirst(beta_a_first, **betaitr);
                allEpsilon = ffg->CheckEpsilonInFirst(**betaitr);
            }
            // Collect First(a)
            if(allEpsilon)
            {
                if(citr->lookahead == GetEndOfFile())
                    beta_a_first.push_back(GetEndOfFile());
                else
                {
                    assert(citr->lookahead != GetEndOfFile() && citr->lookahead != GetEpsilon());
                    ffg->CollectFirst(beta_a_first, *citr->lookahead);
                }

            }
            cerr << "Collected" << endl;

            for(auto fitr = beta_a_first.begin(); fitr != beta_a_first.end();)
            {
                if(*fitr == GetEndOfFile() || *fitr == GetEpsilon() || !isNonterminal(**fitr))
                    fitr++;
                else
                    fitr = beta_a_first.erase(fitr);
            }

            cerr << "Erased" << endl ;

            ProductionMap::iterator bpbegin, bpend;
            std::tie(bpbegin, bpend) = production.equal_range(**citr->item.dot);
            for(auto bpitr = bpbegin; bpitr != bpend; ++bpitr)
            {
                ClosureList deltaList;
                for(auto titr = beta_a_first.begin(); titr != beta_a_first.end(); ++titr)
                {
                    Closure nClosure;
                    nClosure.lookahead = *titr;
                    nClosure.item.prod = bpitr;
                    nClosure.item.dot = nClosure.item.prod->second.begin();
                    deltaList.push_back(nClosure);
                }

                if(MergeListKeepUnique(newClist, deltaList))
                    hasChanged = true;
            }
        }
    }while(hasChanged);
    return newClist;
}

ClosureList ContextFreeGrammar_LR1::GenerateGoto(const ClosureList& closurelist, StringSet::const_iterator x)
{
    cerr << "Generating Goto" << endl ;
    ClosureList gt;

    bool hasChanged = true;
    do
    {
        //cerr << "-Iterating" << endl ;
        ClosureList delta_gt;
        for(auto citr = closurelist.begin(); citr != closurelist.end(); ++citr)
        {

            const Closure & closure = *citr;
            if(closure.item.dot != closure.item.prod->second.end() && *closure.item.dot == x)
            {
                Closure nClosure;
                nClosure.item.prod = closure.item.prod;
                nClosure.item.dot = std::next(closure.item.dot);
                nClosure.lookahead = closure.lookahead;
                delta_gt.push_back(nClosure);
            }
        }
        hasChanged = MergeListKeepUnique(gt, delta_gt);
    }while(hasChanged);

    return GenerateClosure(gt);
}

void ContextFreeGrammar_LR1::Test()
{
    this->Augment();
    /*
    Closure closure;
    closure.item.prod = production.find(*startSymbol);
    closure.item.dot = closure.item.prod->second.begin();
    closure.lookahead = GetEndOfFile();

    ClosureList cl = {closure};
    cl = GenerateClosure(cl);
    PrintClosureList(cl);
    ClosureList gt = GenerateGoto(cl, nonterminal.find("S"));
    PrintClosureList(gt);
    */

    this->GenerateCollection();
    this->PrintCollection();
}

void ContextFreeGrammar_LR1::PrintClosure(const Closure& c, std::ostream& out) const
{
    out << "[" << c.item.prod->first << " ->" ;
    //PrintProductionRight(c.item.prod->second, out);
    for(auto pritr = c.item.prod->second.begin(); pritr != c.item.prod->second.end(); ++pritr)
    {
        out << " " ;
        if(pritr == c.item.dot)
            out << "." ;
        out << **pritr;
    }
    if(c.item.dot == c.item.prod->second.end())
        out << "." ;
    out << "," << SafePrint(c.lookahead) << "]";
}

void ContextFreeGrammar_LR1::PrintClosureList(const ClosureList& cl, std::ostream& out) const
{
    for(auto itr = cl.begin(); itr != cl.end(); ++itr)
    {
        PrintClosure(*itr, out);
        out << ";";
    }
    out << std::endl ;
}

void ContextFreeGrammar_LR1::GenerateCollection()
{
    collection.clear();

    // Start from {[S' -> .S, $]}
    Closure closure;
    closure.item.prod = production.find(*startSymbol);
    closure.item.dot = closure.item.prod->second.begin();
    closure.lookahead = GetEndOfFile();
    ClosureList * pcl = new ClosureList{GenerateClosure({closure})};
    collection.push_back(std::unique_ptr<ClosureList>(pcl));

    bool hasChanged = false;
    do
    {
        hasChanged = false;
        Collection goto_new;
        std::vector <std::pair<Collection::const_iterator, StringSet::const_iterator>> goto_a;

        for(auto citr = collection.begin(); citr != collection.end(); ++citr)
        {
            for(auto titr = terminal.begin(); titr != terminal.end(); ++titr)
            {
                ClosureList * ng = new ClosureList(GenerateGoto(**citr, titr));
                goto_new.push_back(std::unique_ptr<ClosureList>(ng));
                goto_a.push_back(std::make_pair(citr, titr));
            }

            for(auto ntitr = nonterminal.begin(); ntitr != nonterminal.end(); ++ntitr)
            {
                ClosureList * ng = new ClosureList(GenerateGoto(**citr, ntitr));
                goto_new.push_back(std::unique_ptr<ClosureList>(ng));
                goto_a.push_back(std::make_pair(citr, ntitr));
            }
        }

        Collection::iterator citr;
        std::vector <std::pair<Collection::const_iterator, StringSet::const_iterator>>::iterator gitr;
        for(citr = goto_new.begin(), gitr = goto_a.begin(); citr != goto_new.end(); ++citr, ++gitr)
        {
            if(citr->get()->empty())
                continue;
            bool isDuplicated = false;
            for(auto ocitr = collection.begin(); ocitr != collection.end(); ++ocitr)
            {
                if(ocitr->get()->size() != citr->get()->size())
                    continue;
                if(*ocitr->get() == *citr->get())
                {
                    isDuplicated = true;
                    break;
                }
            }

            if(!isDuplicated)
            {
                collection.push_back(std::move(*citr));
                GotoMap[gitr->first][*gitr->second] = std::prev(collection.end());
                hasChanged = true;
            }
        }

    }while(hasChanged);
}


void ContextFreeGrammar_LR1::PrintCollection(std::ostream & out) const
{
    for(auto itr = collection.begin(); itr != collection.end(); ++itr)
    {
        out << "I" << itr - collection.begin() << ":";
        PrintClosureList(*itr->get(), out);
        out << endl ;
    }
}


